During the design phase of an integrated circuit, it is necessary to place cells within the bounds (footprint) of the semiconductor chip layout in accordance with certain design rules. The placement of cells takes into account routing of wires between the cells, pin placement, timing considerations, etc. Certain cells, called “megacells”, occupy a considerably larger area than most cells. Examples of megacells include flip-flops, memories, etc.
When the cells are initially placed, the positions of certain cells, including certain megacells, are considered “fixed” due to design constraints. For example, it is common to fix the position of cells having pins coupled to an edge of the IC chip for connection to external devices.
During the design phase, wires are routed between cells. These wires form “blockages” where cells and megacells cannot be placed. Thus, if the position of a cell or megacell encroaches on a blockage, either the blockage or the cell (or megacell) must be moved. Ordinarily, movement of a blockage is a relatively complex task, because it usually involves movement of numerous other cells and megacells. On the other hand, it is a relatively simple matter to move ordinary cells to accommodate blockages. Therefore, it is common to move ordinary cells rather than blockages. But it is not an altogether easy task to move megacells to accommodate blockages.
Another problem encountered in megacell placement occurs where plural megacells overlap. The size of megacells usually makes it difficult to move megacells after placement of other cells. Moreover, movement of fixed megacells, including flipping and rotation, might adversely affect timing considerations to pins of the megacell, and might adversely affect the space available for routing wires and subsequent cell placement.
Consequently, there is a need for a technique to place megacells to the footprint of an IC chip such that the placement of all megacells is “legal”. As used herein, megacell placement is considered legal if no two megacells intersect, if no megacell occupies area covered by blockages, if fixed megacells are not moved, rotated or flipped, and if there is enough space between megacells to create a legal placement of the remaining cells and blockages.